Data storage systems can be complex, especially when configured to handle large amounts of data. Such systems may comprise multiple subsystems that communicate with one another over a network and that collectively operate to store data and service requests related to the storage of data, such as requests to store or retrieve data. Further, data storage systems are often configured to provide some level of assurances with respect to data durability. Those who utilize data storage systems, for example, typically want the ability to retrieve data at a later time. Accordingly, data storage systems are often configured to utilize redundancy and other techniques to lower the risk of data becoming irretrievable. Despite best efforts, however, the complexity of data storage systems can provide challenges for maintaining data durability. Hardware or software malfunction, programming errors, and malicious behavior, for example, can increase the risk of data loss. Moreover, goals of cost effectiveness and efficiency can often compete with goals for data durability.